package com.leetcode.algorithm.y19.m01;

import java.util.Arrays;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * (done)876. 链表的中间结点
 * (done)496. 下一个更大元素 I
 * (done)883. 三维形体投影面积
 * (done)868. 二进制间距
 * (done)976. 三角形的最大周长
 * @author: jie.deng
 * @time: 2019年1月28日 上午9:16:54
 */
public class MySolution0128 {
	/**
	 * 876. 链表的中间结点
	 * 
     * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
     * 
     * 如果有两个中间结点，则返回第二个中间结点。
     * 
     * 示例 1：
     * 
     * 输入：[1,2,3,4,5]
     * 输出：此列表中的结点 3 (序列化形式：[3,4,5])
     * 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
     * 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
     * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
     * 示例 2：
     * 
     * 输入：[1,2,3,4,5,6]
     * 输出：此列表中的结点 4 (序列化形式：[4,5,6])
     * 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
     *  
     * 
     * 提示：
     * 
     * 给定链表的结点数介于 1 和 100 之间。
	 * @param head
	 * @return
	 */
    public ListNode middleNode(ListNode head) {
		int idx = 1;
		ListNode cur = head;
		while (cur.next != null) {
			idx++;
			cur = cur.next;
		}
		int end = idx / 2 + 1;
		cur = head;
		idx = 1;
		while (idx < end) {
			idx++;
			cur = cur.next;
		}
		return cur;
    }
    
    /**
     * 496. 下一个更大元素 I
     * 给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
     * 
     * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
     * 
     * 示例 1:
     * 
     * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
     * 输出: [-1,3,-1]
     * 解释:
     *     对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
     *     对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
     *     对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
     * 示例 2:
     * 
     * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
     * 输出: [3,-1]
     * 解释:
     *     对于num1中的数字2，第二个数组中的下一个较大数字是3。
     *     对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
     * 注意:
     * 
     * nums1和nums2中所有元素是唯一的。
     * nums1和nums2 的数组大小都不超过1000。
     * @param nums1
     * @param nums2
     * @return
     */
	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;
		int[] nums3 = new int[len1];
		Arrays.fill(nums3, -1);
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				if (nums2[j] == nums1[i]) {
					for (int k = j + 1; k < len2; k++) {
						if (nums2[k] > nums1[i]) {
							nums3[i] = nums2[k];
							break;
						}
					}
					break;
				}
			}
		}
		return nums3;
	}
    

    
    /**
     * 883. 三维形体投影面积
     * 在 N * N 的网格中，我们放置了一些与 x，y，z 三轴对齐的 1 * 1 * 1 立方体。
     * 
     * 每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。
     * 
     * 现在，我们查看这些立方体在 xy、yz 和 zx 平面上的投影。
     * 
     * 投影就像影子，将三维形体映射到一个二维平面上。
     * 
     * 在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。
     * 
     * 返回所有三个投影的总面积。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：[[2]]
     * 输出：5
     * 示例 2：
     * 
     * 输入：[[1,2],[3,4]]
     * 输出：17
     * 解释：
     * 这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。
     * 
     * 示例 3：
     * 
     * 输入：[[1,0],[0,2]]
     * 输出：8
     * 示例 4：
     * 
     * 输入：[[1,1,1],[1,0,1],[1,1,1]]
     * 输出：14
     * 示例 5：
     * 
     * 输入：[[2,2,2],[2,1,2],[2,2,2]]
     * 输出：21
     *  
     * 
     * 提示：
     * 
     * 1 <= grid.length = grid[0].length <= 50
     * 0 <= grid[i][j] <= 50
     * @param grid
     * @return
     */
	public int projectionArea(int[][] grid) {
		int sum = 0;
		int lenR = grid.length;
		int lenC = grid[0].length;
		// 在 xy平面上的投影
		for (int i = 0; i < lenR; i++) {
			for (int j = 0; j < lenC; j++) {
				if (grid[i][j] != 0) {
					sum++;
				}
			}
		}
		// 在 yz平面上的投影
		for (int i = 0; i < lenR; i++) {
			int max = grid[i][0];
			for (int j = 0; j < lenC; j++) {
				if (grid[i][j] > max) {
					max = grid[i][j];
				}
			}
			sum += max;
		}
		// 在 zx平面上的投影
		for (int i = 0; i < lenC; i++) {
			int max = grid[0][i];
			for (int j = 0; j < lenR; j++) {
				if (grid[j][i] > max) {
					max = grid[j][i];
				}
			}
			sum += max;
		}

		return sum;
	}    

    /**
     * 868. 二进制间距
     * 给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。 
     * 
     * 如果没有两个连续的 1，返回 0 。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：22
     * 输出：2
     * 解释：
     * 22 的二进制是 0b10110 。
     * 在 22 的二进制表示中，有三个 1，组成两对连续的 1 。
     * 第一对连续的 1 中，两个 1 之间的距离为 2 。
     * 第二对连续的 1 中，两个 1 之间的距离为 1 。
     * 答案取两个距离之中最大的，也就是 2 。
     * 示例 2：
     * 
     * 输入：5
     * 输出：2
     * 解释：
     * 5 的二进制是 0b101 。
     * 示例 3：
     * 
     * 输入：6
     * 输出：1
     * 解释：
     * 6 的二进制是 0b110 。
     * 示例 4：
     * 
     * 输入：8
     * 输出：0
     * 解释：
     * 8 的二进制是 0b1000 。
     * 在 8 的二进制表示中没有连续的 1，所以返回 0 。
     *  
     * 
     * 提示：
     * 
     * 1 <= N <= 10^9
     * @param N
     * @return
     */
	public int binaryGap(int N) {
		String str = Integer.toBinaryString(N);
		char[] arr = str.toCharArray();
		int idx = 0;
		int maxCnt = 0;
		while (idx < arr.length) {
			// 找第一个1
			while (idx < arr.length && arr[idx] == '0') {
				idx++;
			}
			int fromIdx = idx;
			idx++;
			// 找下一个1
			while (idx < arr.length && arr[idx] == '0') {
				idx++;
			}
			if (idx < arr.length) {
				if (idx - fromIdx > maxCnt) {
					maxCnt = idx - fromIdx;
				}
			}
		}
		return maxCnt;
	}

    /**
     * 976. 三角形的最大周长
     * 给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
     * 
     * 如果不能形成任何面积不为零的三角形，返回 0。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：[2,1,2]
     * 输出：5
     * 示例 2：
     * 
     * 输入：[1,2,1]
     * 输出：0
     * 示例 3：
     * 
     * 输入：[3,2,3,4]
     * 输出：10
     * 示例 4：
     * 
     * 输入：[3,6,2,3]
     * 输出：8
     *  
     * 
     * 提示：
     * 
     * 3 <= A.length <= 10000
     * 1 <= A[i] <= 10^6
     * @param A
     * @return
     */
	public int largestPerimeter(int[] A) {
		int len = A.length;
		int first = 0;
		int second = 0;
		int third = 0;
		for (int i = 0; i < len; i++) {
			first = second;
			second = third;
			int maxIdx = i;
			// 选择最大的元素
			for (int j = i + 1; j < len; j++) {
				if (A[j] > A[maxIdx]) {
					maxIdx = j;
				}
			}
			if (maxIdx != i) {
				// 交换
				A[i] = A[i] ^ A[maxIdx];
				A[maxIdx] = A[i] ^ A[maxIdx];
				A[i] = A[i] ^ A[maxIdx];
			}
			third = A[i];
			if (first != 0 && third + second > first) {
				return third + second + first;
			}
		}
		return 0;
	}

}
